const int MOD=1e9+7;
const int N=5010;
long long dp[N][4];
auto Init=[]()
{
    dp[0][0]=dp[0][1]=dp[0][2]=dp[0][3]=1;
    for(int i=1;i<N;++i)
    {
        dp[i][0]=(dp[i-1][1]+dp[i-1][2])%MOD;
        dp[i][1]=dp[i-1][0]*2%MOD;
        dp[i][2]=(dp[i-1][0]*2+dp[i-1][3])%MOD;
        dp[i][3]=dp[i-1][2]*2%MOD;
    }
    return 0;
}();

class Solution {
public:


long long memo[5001][10];
    

    int knightDialer(int n) {
        if(n==1) return 10;
        
        return (dp[n-1][0]*4+dp[n-1][1]*2+dp[n-1][2]*2+dp[n-1][3])%MOD;
    }
    
const vector<int> NEXT[10]={{4,6},{6,8},{7,9},{4,8},{3,9,0},{},{1,7,0},{2,6},{1,3},{2,4}};
long long memo[5001][10];
    long long dfs(int i,int j)
    {
        if(i==0) return 1;

        long long &res=memo[i][j];
        if(res) return res;

        if(j==0) res=(dfs(i-1,1)+dfs(i-1,2))%MOD;
        else if(j==1) res=dfs(i-1,0)*2%MOD;
        else if(j==2) res=(dfs(i-1,0)*2+dfs(i-1,3))%MOD;
        else res=dfs(i-1,2)*2%MOD;

        return res;
    }

    int knightDialer(int n) {
        if(n==1) return 10;
        
        return (dfs(n-1,0)*4+dfs(n-1,1)*2+dfs(n-1,2)*2+dfs(n-1,3))%MOD;
    }
    
    int dfs(int i,int j)
    {
        if(i==0) return 1;

        int &res=memo[i][j];
        if(res) return res;

        for(auto k:NEXT[j])
        {
            res=(res+dfs(i-1,k))%MOD;
        }
        return res;
    }

    int knightDialer(int n) {
        if(n==1) return 10;
        long long ans=0;
        for(int i=0;i<10;++i)
            ans+=dfs(n-1,i);
        return ans%MOD;
    } 
};